package algorithm.arithmetic.计算整数序列的最大子列和;

/**
 * @author xinchen by 2016/11/28
 * @version 1.0
 */
public class Solution {
    // 给定K个整数组成的序列{ N1，N2,...Nk},“连续子列”被定义为{ Ni,Ni+1...Nj}，其中 1≤i≤j≤K。
    // 最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，
    // 其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
    public static void main(String[] args) {
        // args = new String[]{"6", "-2", "11", "-4", "13", "-5", "-2"};
        int[] N = new int[args.length - 1];
        for (int i = 0; i < N.length; i++) {
            N[i] = Integer.parseInt(args[i + 1]);
        }
        int[][] S = new int[N.length][N.length];
        int max = 0;
        for (int i = 0; i < N.length; i++) {
            for (int j = i; j < N.length; j++) {
                if (j == 0) {
                    S[i][j] = N[j];
                } else {
                    S[i][j] = S[i][j - 1] + N[j];
                }
                if (S[i][j] > max) {
                    max = S[i][j];
                }
            }
        }
        System.out.println(max);

    }
}
